'''
https://leetcode.cn/problems/couples-holding-hands/description/
'''
from typing import List


class UnionFindSet3:
    def __init__(self, n):
        self.father = [i for i in range(n)]
        self.size = [1] * n

    def find(self, i):
        if i != self.father[i]:
            self.father[i] = self.find(self.father[i])
        return self.father[i]

    def union(self, a, b):
        i, j = self.find(a), self.find(b)
        if i == j:
            return
        if self.size[i] <= self.size[j]:
            self.father[i] = j
            self.size[j] += self.size[i]
            self.size[i] = 0
        else:
            self.father[j] = i
            self.size[i] += self.size[j]
            self.size[j] = 0

    def is_same_set(self,a, b):
        return self.find(a) == self.find(b)

class Solution:
    def minSwapsCouples(self, row: List[int]) -> int:
        n = len(row)
        ufs = UnionFindSet3(n // 2)
        for i in range(0, n, 2):
            ufs.union(row[i] // 2, row[i + 1] // 2)
        ans = 0
        for e in ufs.size:
            if e < 2: continue
            ans += e - 1
        return ans

